package weitu;

import java.util.Arrays;

/**
 * 位图
 * 使用比特位来表示一个数字
 * 其中包含一个字节数组，用来储存不同大小范围内的数字，
 * 通过将指定字节置为空，就可以做到存储指定的数字
 * 空间利用率极高，相当于一个比特为可以储存一个字节
 */
public class MyBitset {

    int userSize;
    int DefaultSpace;
    byte[] elem;//字节数组


    public MyBitset() {
        elem = new byte[1];
        this.userSize = 0;
        DefaultSpace = 1;
    }

    public MyBitset(int n) {//n是字节大小
        elem = new byte[n % 8 + 1];//加一向上取整
        this.userSize = 0;
        DefaultSpace = n + 1;
    }

    public void add(int n) {
        if (n < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        //得到该值对于区间的下表
        int byteIndex = n / 8;

        if (byteIndex + 1 > DefaultSpace) {//byteIndex 是重0开始计算的
            expandSpace(byteIndex);
        }
        //将指定比特为再置为1
        int bitIndex = n % 8;
        elem[byteIndex] |= (byte) (1 << bitIndex);
        userSize++;
    }

    private void expandSpace(int byteIndex) {
        elem = Arrays.copyOf(elem, byteIndex + 1);
    }

    public boolean contain(int n) {
        int byteIndex = n / 8;
        if (byteIndex >= DefaultSpace) {
            return false;
        }
        int bitIndex = n % 8;
        //& 有0为0 俩一为1 若存在的话会将elem对于的值变为1 << bitIndex的值
        return ((1 << bitIndex) & elem[byteIndex]) == 1 << bitIndex;
    }

    //将这个值置为0
    public void clear(int n) {
        int byteIndex = n / 8;
        if (byteIndex > DefaultSpace) {
            return;
        }
        int bitIndex = n % 8;

        elem[byteIndex] &= (byte) ~(1 << bitIndex);
    }


    //使用位图排序
    public int[] sort() {
        //对elem排序
        int[] endArr = new int[this.userSize];
        int Index = 0;
        for (int i = 0; i < this.elem.length; i++) {

            for (int j = 0; j < 8; j++) {//遍历每个比特位
                int bitIndex = 1 << j;
                //是否再bitIndex这个位为1 存在就储存这个值
                if ((bitIndex & this.elem[i]) == bitIndex) {
                    endArr[Index++] = 8 * i + j;
                }
            }
        }
        return endArr;
    }

    public int[] sort(int[] array) {
        MyBitset arr = new MyBitset();
        //储存这个数组
        for (int i = 0; i < array.length; i++) {
            arr.add(array[i]);
        }

        int[] endArr = new int[arr.userSize];
        int Index = 0;
        for (int i = 0; i < arr.elem.length; i++) {

            for (int j = 0; j < 8; j++) {//遍历每个比特位
                int bitIndex = 1 << j;
                //是否再bitIndex这个位为1 存在就储存这个值
                if (((bitIndex) & arr.elem[i]) == bitIndex) {
                    endArr[Index++] = 8 * i + j;
                }
            }
        }
        return endArr;
    }
}
